//力扣第20题
public class Test {
}
class solution {
    public int change(char c){
        int a=0;
        switch (c){
            case '(': a=1;break;
            case '[': a=2;break;
            case '{': a=3;break;
            case ')': a=-1;break;
            case ']': a=-2;break;
            case '}': a=-3;break;
        }
        return a;
    }
    public boolean isValid(String s) {
        int arr[]=new int[5000];
        int i=0,a;
        for (int k = 0; k < s.length(); k++) {
            if((a=change(s.charAt(k)))<0){
                if(i==0)
                    return false;
                if(a+arr[i-1]!=0)
                    return false;
                i--;
            }else{
                arr[i]=a;
                i++;
            }
        }
        if(i==0)
            return true;
        else
            return false;
    }
}

//////////////////////////////////////
//class solution {
//    // Leetcode 22. Generate Parentheses
//    // Backtracking
//    // Time Complexity: Hard To Say
//    // Space Complexity: Hard To Say
//    public List<String> generateParenthesis(int n) {
//        List<String> result = new ArrayList<>();
//        backtracking(n, result, 0, 0, "");
//        return result;
//    }
//
//    private void backtracking(int n, List<String> result, int left, int right, String str) {
//        if (right > left) {
//            return;
//        }
//        if (left == n && right == n) {
//            result.add(str);
//            return;
//        }
//
//        if (left < n) {
//            backtracking(n, result, left+1, right, str+"(");
//        }
//
//        if (right < left) {
//            backtracking(n, result, left, right+1, str+")");
//        }
//    }
//}
